package 力扣.回溯;

import java.util.ArrayList;
import java.util.List;

public class 子集78 {
    public List<List<Integer>> subsets(int[] nums) {
        if (nums == null || nums.length == 0){
            return new ArrayList<>();
        }
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> box = new ArrayList<>();
        backTrace(nums,0,ans,box);
//        ans.add(new ArrayList<>());
        return ans;
    }

    private void backTrace(int[] nums, int i, List<List<Integer>> ans, List<Integer> box) {
        final  int N = nums==null ? 0 : nums.length;
        ans.add(new ArrayList<>(box));//什么样子的箱子是我们想要的？
        if (i >= N){//这个人还存在码
            return;
        }
        //这个人开始选宝石了——宝石该怎么选呢？核心
        for (int j = i; j < N; j++) {
            int te = nums[j];
            box.add(te);
            backTrace(nums, j + 1, ans,box);//注意是j + 1,也就是跟i无关。
            box.remove(box.size() - 1);
        }
    }

    public List<List<Integer>> subsets2(int[] nums) {
       if (nums == null || nums.length == 0){
           return new ArrayList<>();
       }
       List<List<Integer>> ans = new ArrayList<>();
       List<Integer> box = new ArrayList<>();
       backTrace2(nums,0,ans,box);
       return ans;
    }

    private void backTrace2(int[] nums, int i, List<List<Integer>> ans, List<Integer> box) {
         ans.add(new ArrayList<>(box));
         if (i >= nums.length){
             return;
         }
        for (int j = i; j < nums.length; j++) {
            box.add(nums[j]);
            backTrace2(nums, j + 1, ans, box);
            box.remove(box.size() - 1);
        }
    }
}
